package third

import (
	"sort"
	"strings"
)

/*
	输入一个字符串，打印出该字符串中字符的所有排列。

	你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

	示例:

	输入：s = "abc"
	输出：["abc","acb","bac","bca","cab","cba"]

	限制：

	1 <= s 的长度 <= 8

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

func Permutation(s string) []string {
	return permutation(s)
}

func permutation(s string) []string {
	s1 := strings.Split(s, "")
	sort.Strings(s1)
	s = strings.Join(s1, "")
	m := make(map[int]bool)
	result := make([]string, 0)
	_permutations(s, "", 0, m, &result)
	return result
}

func _permutations(s string, cur string, index int, visited map[int]bool, result *[]string) {
	if index == len(s){
		*result = append(*result, cur)
		return
	}
	for i := 0; i < len(s); i++ {
		if visited[i] {
			continue
		}
		if i > 0 && s[i] == s[i-1] && visited[i-1] {
			continue
		}
		visited[i] = true
		_permutations(s, cur+string(s[i]), index+1, visited, result)
		visited[i] = false
	}
}

/*
	1. 对字符串进行排序
	2. 使用回溯法
		注意、因为可能存在重复的字符、比如aab、所以对于已经排好序的字符串、可以有如果规则
		2.1 当前元素已经访问、跳过
		2.2 当前元素未访问、但前一个元素已经访问且前一个元素和当前元素相等、跳过
*/
